# -*- coding: utf-8 -*-1
import aima.search as s
#Definimos el estado : Usaremos una tupla que tendra como valor (Cant misioneros, Cant Canibales, Bool:Si la canoa esta a izquierda)

class sonsin(s.Problem): #Redefinimos la clase problem
        def accion(self, estado,accion): return (estado[0]+accion[0], estado[1]+accion[1], not(estado[2])) #devuelve el estado en que quedaria el sistema si aplicamos una accion
        def validar(self, estado): return (estado[0], estado[1]) in [(0,0), (0,1), (1,1), (2,2), (3,2), (3,3), (3,1), (3,0), (0,3), (0,2)] #Revisa si el estado que pasamos es valido para el sistema, pensado todas las opciones en las dos orillas
        def successor(self, e):#Siempre lo que movemos es la posicion vacia (0)
                res= [] #Creamos la lista de sucesores para el estado actual.
                if e[2]: lista = [(-1,-1), (-2,0), (0,-2), (-1,0), (0,-1)] #llevamos gente a otra orilla (M,C)
                else: lista= [(1,1), (2,0), (0,2), (1,0), (0,1)] #Traer gente de otra orilla (M,C)
                for a in lista: #Para cada accion de la lista objetivo
                        if self.validar(self.accion(e,a)): res.append((str(a), self.accion(e,a))) #Revizamos si es valido el estado en que quedaria el sistema si realizamos esa accion y si es asi, agregamos esa tupla
                return res #retornamos la lista de todas las acciones posibles

def heuristica(nodo): #La heuristica que utilizaremos suma la cantidad que faltan cruzar
        return (nodo.state[0]+nodo.state[1]-1) #y le resta uno, que seria el costo del ultimo.

if __name__ == '__main__':
        EI = (3,3,True) #Asi comienza el problema, los 3 canibales y los 3 misioneros en la orilla inicial
        EO= (0,0,False) #El estado objetivo es quitar toda la gente de la orilla inicial / No importa el costo.
        agente= sonsin(EI,EO) #Instanciamos al agente
        path= s.best_first_graph_search(agente, heuristica)#Pedimos que encuentre el camino segun un algoritmo
        if path is None: print 'Sin solucion'
        else:
                print 'Solucionado'
                for m in path.path()[::-1]: print str(m.action) + ":" + str(m.state)
                
